/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/reorder-list
   @Language: C++
   @Datetime: 16-02-09 08:24
   */

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
	/**
	 * @param head: The first node of linked list.
	 * @return: void
	 * Tip: Using two point step1, step2 traversal list
	 *      to get middle of list (step1)
	 *      reverse part-list from step1 to end
	 *      now merge two list: head and reversed step1-end
	 */
	void reorderList(ListNode *head) {
		// write your code here
		if (head==NULL || head->next==NULL) return;
		ListNode H(-1),*step1,*step2,*t;
		H.next=head;
		// find middle node in &H
		for(step1=step2=&H; step2; step1=step1->next){
			step2 = step2->next;
			if (step2==NULL) break;
			step2 = step2->next;
		}   // step1->next is middle node in head
		head = step1->next;
		step1->next = NULL;	// cut down part-list
		// splits into two lists: H.next, head
		// reverse head
		for(step1=head,head=NULL; step1;){
			t = step1->next;
			step1->next = head;
			head = step1;
			step1 = t;
		}   // head is reversed list's head
		// merge two lists: H.next, head, first node is H.next
		for(step1=H.next; head;){
			step2 = step1->next;
			t = head->next;
			step1 = step1->next = head;
			step1 = step1->next = step2;
			head = t;
		}
	}
};
